CPE 426 Computer Networks
Chapter 9:
Text Chapter 18&27: Internet
Routing Part I:
TOPICS
Chapter 27: Internet Routing and Routing Protocols
27.1 Introduction
27.2 Static vs Dynamic Routing
Extra: Router Configuration in Network
27.3 Static Routing and Default Route
Extra: Examples of Static Routing
BREAK
27.4 Dynamic Routing and Router
27.5 Routing in Global Internet
27.6 Autonomous System Concept
27.7 Two Types of Routing Protocol
27.8 Routes and Data Traffic
Extra: Bellman-Ford Algorithm Review
Extra: Dijkstra Algorithm Review
Chapter 27:Internet Routing and
Routing Protocol
ล ักษณะการส่ง Packet ใน IP Network จะส่ง
ทีละ Hop จาก Network หนึ่ง ไปย ังอีก
Network หนึ่ง
Router จะทําหน้าที่ด ังกล่าว เนื่องจาก Router เป็นต ัวเชื่อมระหว่าง Network
การส่งจะดูที่ส่วน Prefix ของ IP Address
ด ังน ั้น Router จะต้อง Run IP Protocol คือ
ทํางานในระด ับ Layer 3
ที่ Router จะมีตารางชื่อ Routing Table ที่
กําหนด IP Address ของ Next Hop
Chapter 27: 27.2 Static vs
Dynamic Routing
การทํา Routing ทําได้สองแบบ
Static Routing: หมายถึงตาราง Routing Table ของ
Router แต่ละตัวจะไม่เปลี่ยน ปกติตารางนี้จะถูกกําหนด
จาก Network Administration
คือตารางนี้จะได ้จากการทํา Configuration ของ Router
Dynamic Routing: หมายถึงตาราง Routing Table
สามารถเปลี่ยนได ้ ตามสภาวะความคับคั่งของ Network ขณะนั้น โดยมันจะมีการ Update ตลอดเวลา
ตารางนี้ได ้จากการกําหนดให ้ Router ทําการ Run Routing Protocol
ในแต่ละ Routing Protocol ตัว Router จะทําการแลกเปลี่ยน
ข ้อมูลกันเอง โดยผู ้ดูแล Network ไม่ต ้องมาเกี่ยวข ้อง จากนั้น
Router แต่ละตัวจะสร ้างตาราง Routing Table จากข ้อมูลที่มัน
รวบรวมได ้ เมื่อข ้อมูลที่ได ้รับเปลี่ยน เนื่องจาก Network เปลี่ยน
มันจะคํานวณตารางใหม่ และปรับให ้เข ้ากับสภาพของ Network ที่
เปลี่ยนไป
Chapter 27: 27.3 Static Routing
in Host and Default Route
ข้อดีของ Static Routing คือง่าย และไม่ต้องใช้
Routing Software(Router จะทํางานน้อยลง)
นอกจากนี้จะไม่ใช้ Resource ของ Network เพราะ
Router ไม่ต้องแลกเปลี่ยนข้อมูลก ัน
แต่ข้อเสียคือ ตารางเปลี่ยนไม่ได้ ถ้ามี Link Down หรือ Router Down เส้นทางน ั้นจะใช้ไม่ได้ ทําให้การ
ส่งข้อมูลที่กําหนดเส้นทางน ั้นหยุดชะง ัก
นอกจากนี้แล ้ว Static Routing จะจํากัดที่ Network ขนาดเล็ก เช่น
ระหว่าง LAN ขององค์กร การเชื่อมต่อกับ Internet จะไม่ใช ้ Static Routing
หรือใช ้กําหนดสําหรับ Host ที่เชื่อมต่อกับ Network ที่มีทางออก
ผ่าน Router ตัวเดียว(คือค่า Gateway)
การใช้ Static Route ควรมีการกําหนด Default
Route เสมอ
การทํา Static Route ต้องตรวจสอบให้ดีว่าจะไม่มี
Route Loop
Chapter 27: 27.3 Static Routing
in Host and Default Route
การกําหนด Interface สําหร ับ
Router
แต่ละ Interface ของ Router จะต้องมี IP Address ที่ตรงก ับแต่ละ Network ที่ Interface เชื่อมต่อ
(Prefix เหมือนก ัน แต่ Suffix ต่างก ัน)
58.42.96.0/19
58.42.96.1
58.42.96.2
200.18.95.1
195.3.0.193
R1
R2
200.18.95.0/24
195.3.0.192/26
R3
R4
195.3.0.194
200.18.95.2
70.12.0.1
70.12.0.2
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
สายที่เชื่อมต่อโดยตรงระหว่าง Router จะต้องถือเป็น
หนึ่ง Network เช่นก ัน แต่ Network นี้เป็นแค่ทางผ่าน
ของข้อมูล ไม่จําเป็นต้องกําหนดใน Routing Table 58.42.96.0/19
58.42.96.1
200.18.95.1 R1
R4 195.3.0.193
R2
200.18.95.0/24
195.3.0.192/26
R3
70.12.0.1
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
สายระหว่าง Router สามารถ Subnet จาก Private IP ได้ และ
ต้องการเพียงสอง Host Address ซึ่งปกติจะใช้ /30 ก็พอ เช่น Sub จาก 192.168.100.0/24 จะได้ 64 Subnet
Subnet 192.168.100.4/30 : Host Range 192.168.100.5-192.168.100.6; Broadcast 192.168.100.7
192.168.100.4/30
58.42.96.0/19
192.168.100.8/30
58.42.96.1
.6
.9
R1 .5
.10 R4
200.18.95.1
195.3.0.193
R2
200.18.95.0/24
195.3.0.192/26
.18
R3
.13
.17
.14
70.12.0.1
192.168.100.12/30
192.168.100.16/30
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
การกําหนด Static Routing Table ให้ก ับ Router แต่ละต ัวทําได้จาก
การกําหนดเส้นทางส่งข้อมูลจาก Router ไปย ังทุกๆ Network (Network ที่เป็น Transit ไม่ต้องกําหนด เพราะไม่มี Host ปลายทาง) จากน ั้นกําหนดเส้นทางหนึ่งให้เป็น Default Route เช่น R1
58.42.96.0/19
58.42.96.1
.6
.9
192.168.100.4/30
192.168.100.8/30
.5
.10
200.18.95.1
R2
195.3.0.193
200.18.95.0/24
R1
R4
195.3.0.192/26
.18
.13
R3
192.168.100.12/30
192.168.100.16/30
.17
.14
70.12.0.1
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
NW
Mask
Next Hop
200.18.95.0
255.255.255.0
Direct
70.12.0.0
255.255.0.0
192.168.100.17
58.42.96.0
255.255.224.0
192.168.100.6
195.3.0.192
255.255.255.192 192.168.100.6
0.0.0.0
0.0.0.0
192.168.100.17
58.42.96.0/19
58.42.96.1
.6
.9
192.168.100.4/30
192.168.100.8/30
.5
.10
200.18.95.1
R2
195.3.0.193
200.18.95.0/24
R1
R4
195.3.0.192/26
.18
.13
R3
192.168.100.12/30
192.168.100.16/30
.17
.14
70.12.0.1
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
R2 Routing Table
58.42.96.0/19
58.42.96.1
.6
.9
192.168.100.4/30
192.168.100.8/30
.5
.10
200.18.95.1
R2
195.3.0.193
200.18.95.0/24
R1
R4
195.3.0.192/26
.18
.13
R3
192.168.100.12/30
192.168.100.16/30
.17
.14
70.12.0.1
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
R3 Routing Table
58.42.96.0/19
58.42.96.1
.6
.9
192.168.100.4/30
192.168.100.8/30
.5
.10
200.18.95.1
R2
195.3.0.193
200.18.95.0/24
R1
R4
195.3.0.192/26
.18
.13
R3
192.168.100.12/30
192.168.100.16/30
.17
.14
70.12.0.1
70.12.0.0/16
การกําหนด Interface สําหร ับ
Router
R4 Routing Table
58.42.96.0/19
58.42.96.1
.6
.9
192.168.100.4/30
192.168.100.8/30
.5
.10
200.18.95.1
R2
195.3.0.193
200.18.95.0/24
R1
R4
195.3.0.192/26
.18
.13
R3
192.168.100.12/30
192.168.100.16/30
.17
.14
70.12.0.1
70.12.0.0/16
Chapter 27: 27.4 Dynamic
Routing and Router
ปกต ิ Router ใน Internet จะใช้ Dynamic
Routing
เพื่อให ้มีการแลกเปลี่ยน Routing Information ระหว่าง
กัน
Static Routing อาจจะถูกใช้ในกรณีที่
Customer เชื่อมต่อก ับ ISP ผ่าน Router ซึ่ง
ในกรณีนี้มีทางออก Internet เพียงทางเดียว
และไม่จําเป็นต้องใช้ Dynamic Routing
หรือ Static Routing อาจจะใช้ภายในองค ์กร
เพื่อเชื่อมต่อ LAN หลายๆวงภายในอาคาร
Chapter 27: 27.4 Dynamic
Routing and Router
Router จะรู้จ ัก Network ที่เป็น Direct Connect เท่าน ั้น
การที่ Router จะรู้จ ัก Network อื่น ม ันจะต้องเรียนรู้
มาจาก Router ต ัวอื่นที่ต่อโดยตรงก ับ Network น ั้น
ใน Static Routing จะไม่มีวิธีที่ Router จะเรียนรู้ได้
ด ังน ั้นการเรียนรู้ต้องมีการกําหนดจาก Software ใน
Routing Protocol ใน Dynamic Routing
ด้วยการเรียนรู้นี้เอง ทําให้ Router สามารถปร ับตาราง
ของตนได้อย่างเหมาะสม ตามสภาพ Network เป็นผล
ให้ตาราง Routing เป็น Dynamic
Chapter 27: 27.4 Dynamic
Routing and Router
จากรูป R1 รู้จ ัก 200.18.95.0/24 และ
58.42.96.0/19 แต่ไม่รู้จ ัก 195.3.0.192/26
R2 รู้จ ัก 58.42.96.0/19 และ 195.3.0.192/26 แต่ไม่
รู้จ ัก 200.18.95.0/24
R1 และ R2 แลกเปลี่ยนข้อมูลก ันผ่าน 58.42.96.0/19
ทําให้ Router แต่ละต ัวรู้จ ัก Network อื่นๆ
ถ้า 195.3.0.192 เกิดล่ม R2 จะรู้ และสามารถบอก
ต่อไปย ัง R1 ได้ ว่า 195.3.0.192/26 Unreachable
ถ้า R2 ล่ม ทําให้ R1 ไม่สามารถติดต่อได้ ด ังน ั้น R1 จะ
Mark ว่า 195.3.0.192/26 เป็น Unreachable เช่นก ัน
R1
R2
200.18.95.0/24
58.42.96.0/19
195.3.0.192/26
Chapter 27: 27.5 Routing in
Global Internet
Internet ประกอบด้วย Router มากมาย ถ้าจะให้
Router ทุกต ัวแลกเปลี่ยนข้อมูลก ับ Router ทุกต ัว จะ
ทําให้ Routing Traffic มีมหาศาล
เพื่อจําก ัดจํานวน Traffic ใน Internet จะใช้การทํา
Routing แบบเป็นลําด ับช ั้น (Hierarchy) โดยมีการ
แบ่งกลุ่มของ Router และมีการแลกเปลี่ยนข้อมูล
ภายในกลุ่ม จากน ั้นจะมี Router ที่เป็นต ัวแทนของ
กลุ่มทําการแลกเปลี่ยนข้อมูลก ับภายนอก
Routing Protocol ภายในกลุ่ม จะแตกต่างจาก
Routing Protocol ระหว่างกลุ่ม
ขนาดของกลุ่มจะไม่จํากัด ขึ้นอยู่กับขนาดขององค์กร
แต่ละองค์กรที่เป็นเจ ้าของกลุ่ม มีสิทธิจะเลือก Routing Protocol อย่างไรก็ได ้ ที่อยู่ภายในกลุ่ม
แต่ Routing Protocol ที่ใช ้แลกเปลี่ยนข ้อมูลระหว่างกลุ่มจะต ้อง
เป็น Protocol เดียวกัน
Chapter 27: 27.6 Autonomous
System Concept
แต่ละกลุ่มของ Router ที่ดูแลจ ัดการ
โดยองค์กรเดียว เราเรียกว่า
Autonomous System (AS)
อาจจะเป็นหนึ่งองค์กร หรือ หนึ่ง ISP
องค์กรหนึ่งอาจจะแบ่งกลุ่มของ Router เป็น
หลาย AS ก็ได ้
Router ภายใน AS จะมีการแลกเปลี่ยน Routing
Information กัน
Chapter 27: 27.7 Two Type of
Internet Routing Protocol
27.7.1 Interior Gateway
Protocols(IGP)
Router ภายใน AS จะใช ้ Interior Gateway
Protocol (IGP) ในการแลกเปลี่ยน Routing
Information
แต่ละ AS มีสิทธิ์ที่จะเลือก IGP อันใดก็ได ้
RIP
OSPF
IGRP (Cisco)
EIGRP (Cisco)
Chapter 27: 27.7 Two Type of
Internet Routing Protocol
27.7.2 Exterior Gateway
Protocols(EGP)
Router ในแต่ละ AS จะใช ้ EGP ในการ
แลกเปลี่ยน Routing Information กับ Router
ในอีก AS หนึ่ง
EGP ปกติจะซับซ ้อนกว่า IGP แต่ว่าการใช ้งาน
จะยืดหยุ่นกว่า และมี Overhead ตํ่ากว่า
EGP จะสรุป Routing Information ในแต่ละ AS
ก่อนที่จะส่งไปให ้อีก AS หนึ่ง
การส่ง Routing Information ออกนอก AS สามารถ
กําหนดว่าข ้อมูลใดให ้ส่ง หรือไม่ให ้ส่งได ้
Chapter 27: 27.7 Two Type of
Internet Routing Protocol
27.7.3 ต ัวอย่างการใช้งาน IGP และ EGP
Router R1 จะ Run ทั้ง IGP1 และ EGP
Router R4 จะ Run ทั้ง IGP2 และ EGP
Chapter 27: 27.7 Two Type of
Internet Routing Protocol
27.7.4 Optimum Routes, Routing
Metrics and IGP
ปกติเส ้นทางส่งข ้อมูลใน Internet จะมีหลายเส ้นทาง
Router จะเลือกเส ้นทางที่ดีที่สุด (Optimal Routes)
Remote Application อาจจะเป็นเส ้นทางที่ Delay ตํ่าสุด
Web Application อาจเป็นเส ้นทางที่ Throughput สูงสุด
Webcast หรือ Real-Time อาจเป็นเส ้นทางที่ Jitter ตํ่าสุด
เราใช ้คําว่า Routing Metric เป็นตัววัดราคาของการส่ง
ในแต่ละเส ้นทาง
อาจจะวัดจาก Delay, Throughput หรือ Jitter หรือผสมกัน
แต่ปกติใน Internet จะใช ้ Metric สองตัวร่วมกัน
Hop Count (จํานวน Network หรือ Router ที่ผ่าน)
Administrative Cost (กําหนดเองจาก Administrator) เพื่อ
ควบคุมให ้เส ้นทางส่งข ้อมูลเป็นไปตามต ้องการ
เช่นกําหนดเส ้นทาง 4 Hop ให ้มี Administrative Cost ตํ่ากว่า
เส ้นทางสอง Hop เพื่อบังคับให ้ข ้อมูลส่งไปทางนี้
Chapter 27: 27.7 Two Type of
Internet Routing Protocol
27.7.4 Optimum Routes, Routing Metrics and
IGP
การหาเส ้นทางของ IGP จะใช ้ Routing Metric
EGP จะไม่ใช ้
เนื่องจากแต่ละ AS ใช ้ IGP ต่างกัน และใช ้ Metric ต่างกัน ไม่สามารถ
เปรียบเทียบได ้
ดังนั้น EGP จะไม่พยายามหา Optimal Path มันเพียงหาเส ้นทางส่ง
ข ้อมูลเท่านั้น
Throughput = 15 Mbps
AS 15
AS 1
AS 100
AS 70
Hop = 10
Chapter 27: 27.8 Routes and
Data Traffic
Data Traffic จะมีท ิศทางการใหลสวน
ทางก ับ Routing Traffic
Least Cost Path Algorithms
ดูรายละเอียดบทที่ 18 18.12-18.13
ดูจาก Course Notes วิชา CPE 326
ดูจาก Course Notes วิชา CPE 231
เรื่อง Graph
มีสอง Algorithm ที่ให้คําตอบเหมือนก ัน แต่ใช้วิธี
คํานวณต่างก ัน
ดังนั้นจะใช ้ข ้อมูลจาก Routing Information ต่างกัน
กําเนิดเป็นวิธีการ Routing สองแบบ
Distance Vector Routing จะใช ้ Bellman-Ford Algorithm
ในการนี้ Router จะแลกเปลี่ยนตาราง Routing Table เฉพาะกับเพื่อนบ ้าน
เท่านั้น ข ้อมูลจะ Propagate ทีละ Router เมื่อถึงเวลาแลกตาราง เช่น
RIP(Routing Information Protocol)
Link-State Routing จะใช ้ Dijkstra Algorithm
ในการนี้ Router จะส่ง Link State ของตนเอง (เฉพาะ Direct Connect) ไปให ้กับทุกๆ Router แต่ละ Router จะรวบรวม Link State Database และสร ้าง Topology ของทั้ง Network จากนั้นมันจะสร ้าง Shortest Path First Tree โดยตัวมันเป็น Root ไปยัง Router ทุกๆตัว
Least Cost Path Algorithms
NW3
NW2
R3
R2
NW4
R4
R5
NW7
R1
R6
NW1
R7
R9
R8
NW5
NW6
1. การส่งข้อมูลจาก Host หนึ่ง ไปย ังอีก Host หนึ่ง กระทําผ่าน Router ถ้าอยู่คนละ Network การหาเส้นทางคือหาเส้นทางจาก Router หนึ่งไปย ัง
อีก Router หนึ่ง ที่ Network น ั้นเชื่อมต่ออยู่
Least Cost Path Algorithms
R3
R2
R4
R5
R1
R6
R7
R9
R8
2. Cost ที่ส่งระหว่าง Router ไปและกล ับไม่จําเป็นต้องเท่าก ัน เพราะขึ้นอยู่
ก ับ Queue ที่ Interface ของ Router ต้นทาง ไม่ใช่ปลายทาง เราแสดง
ค่า Cost ระหว่าง Router ที่มีเส้นเชื่อมต่อ โดยใช้ Cost Matrix
Least Cost Path Algorithms
R3
5
1
R2
R4
4
2
2
1
R5
5
2
2
3
4
3
4
4
1
3 3 3
R1
R6
6
2
R7
4
5
5
1
R9
2 1
3
R8
5
2
3
2. Cost ที่ส่งระหว่าง Router ไปและกล ับไม่จําเป็นต้องเท่าก ัน เพราะขึ้นอยู่
ก ับ Queue ที่ Interface ของ Router ต้นทาง ไม่ใช่ปลายทาง เราแสดง
ค่า Cost ระหว่าง Router ที่มีเส้นเชื่อมต่อ โดยใช้ Cost Matrix (W)
Least Cost Path Algorithms
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
8
5
∞
∞
∞
∞
1
∞
-
2
9
∞
∞
∞
3
∞
∞
3
3
-
2. Cost ที่ส่งระหว่าง Router ไปและกล ับไม่จําเป็นต้องเท่าก ัน เพราะขึ้นอยู่
ก ับ Queue ที่ Interface ของ Router ต้นทาง ไม่ใช่ปลายทาง เราแสดง
ค่า Cost ระหว่าง Router ที่มีเส้นเชื่อมต่อ โดยใช้ Cost Matrix (W)
Bellman-Ford Algorithm
Definitions
Find shortest paths from given node subject to constraint that paths contain at most one link
Find the shortest paths with a constraint of paths of at most two links
And so on
s = source node
w(i, j) = link cost from node i to node j
w(i, i) = 0
w(i, j) = ∞ if the two nodes are not directly connected
w(i, j) ≥ 0 if the two nodes are directly connected
h = maximum number of links in path at current stage of the algorithm
Lh(n) = cost of least-cost path from s to n under constraint of no more than h links
Bellman-Ford Algorithm
Method
Step 1 [Initialization]
L0(n) = ∞, for all n ≠ s
Lh(s) = 0, for all h
Step 2 [Update]
For each successive h ≥ 0
For each n ≠ s, compute
Lh+1(n)=minj[Lh(j)+w(j,n)]; ∀j
Connect n with predecessor node j that achieves minimum
Eliminate any connection of n with different
predecessor node formed during an earlier
iteration
Path from s to n terminates with link from j to n
Example: Bellman Ford จาก Node
1 (h=0: Initialization: s=1)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไปทุกๆ Node = Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L0(n)=∞; n = 2,..,9: L0(1)=0
9
∞
∞
∞
3
∞
∞
3
3
-
Example: Bellman Ford จาก Node
1 (h=1: Initialization: s=1)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไปทุกๆ Node = Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L0(n)=∞; n = 2,..,9: L0(1)=0
9
∞
∞
∞
3
∞
∞
3
3
-
คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]
L1(2)=minj[L0(j)+w(j,2)]; j = 1,..,9
=min[L0(1)+w(1,2),L0(2)+w(2,2),L0(3)+w(3,2),…,L0(9)+w(9,2)]
=min j = 1, path = 1-2, cost = 3
L1(3)=minj[L0(j)+w(j,3)]; j = 1,..,9
=min[L0(1)+w(1,3),L0(2)+w(2,3),L0(3)+w(3,3),…,L0(9)+w(9,3)]
=all infinity
Example: Bellman Ford จาก Node
1 (h=2: n=2,3)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไป Node 3,4,5,7,9= Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0
9
∞
∞
∞
3
∞
∞
3
3
-
คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]
L2(2)=minj[L1(j)+w(j,2)]; j = 1,..,9
=min[L1(1)+w(1,2),L1(2)+w(2,2),L1(3)+w(3,2),…,L1(9)+w(9,2)]
=min j = 1, path = 1-2, cost = 3
L2(3)=minj[L1(j)+w(j,3)]; j = 1,..,9
=min[L1(1)+w(1,3),L1(2)+w(2,3),L1(3)+w(3,3),…,L1(9)+w(9,3)]
=min j=2, path = 1-2 plus 2-3 = 1-2-3, cost = 3+5=8
Example: Bellman Ford จาก Node
1 (h=2: n=5,7)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไป Node 3,4,5,7,9= Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0
9
∞
∞
∞
3
∞
∞
3
3
-
คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]
L2(5)=minj[L1(j)+w(j,5)]; j = 1,..,9
=min[L1(1)+w(1,5),L1(2)+w(2,5),L1(3)+w(3,5),…,L1(6)+w(6,5),..,L1(9)+w(9,5)]
=min(3+1,6+3)=4 (j=2, path = 1-2-5, cost = 4)
L2(7)=minj[L1(j)+w(j,7)]; j = 1,..,9
=min[L1(1)+w(1,7),L1(2)+w(2,7),…,L1(6)+w(6,7),…,L1(9)+w(9,7)]
=min j=6, path = 1-6 plus 6-7 = 1-6-7, cost = 6+2=8
Example: Bellman Ford จาก Node
1 (h=2: n=6)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไปทุกๆ Node = Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0
9
∞
∞
∞
3
∞
∞
3
3
-
คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]
L2(6)=minj[L1(j)+w(j,6)]; j = 1,..,9
=min[L1(1)+w(1,6),…, L1(8)+w(8,6),..,L1(9)+w(9,6)]
= j=8; Path 1-8+8-6 ถูกกว่า Path 1-6
Example: Bellman Ford จาก Node
1 (h=2: n=8)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไปทุกๆ Node = Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0
9
∞
∞
∞
3
∞
∞
3
3
-
คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]
L2(8)=minj[L1(j)+w(j,8)]; j = 1,..,9
=min[L1(1)+w(1,8),…, L1(6)+w(6,8),..,L1(9)+w(9,8)]
=Path ไม่เปลี่ยน
กรณี n=9 พบว่า Path 1-8-9 มีอันเดียวที่มี 2 Hop
Example: Bellman Ford จาก Node
1 (h=3)
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
Cost R1 ไป Node 4 = Infinity
8
5
∞
∞
∞
∞
1
∞
-
2
L2(2)=3; L2(3)=7; L2(5)=4; L2(6)=6
9
∞
∞
∞
3
∞
∞
3
3
-
L2(7)=8; L2(8)=2; L2(9)=4: L2(1)=0
คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]
L3(5)=minj[L2(j)+w(j,5)]; j = 1,..,9
=min[L2(1)+w(1,5),L2(2)+w(2,5),L2(3)+w(3,5),..,L1(9)+w(9,5)]
=Path ไม่เปลี่ยน
Path ไป R7 ไม่เปลี่ยน แม ้ว่า Path 1-2-5-7 จะเท่ากัน
Path ไป R3 เปลี่ยน จาก 1-2-3 เป็น 1-2-5-3, Path R4 = min(1-2-3-4,1-8-9-4)
Example: Bellman Ford จาก Node
1 (h=4)
R3
1
2
3
4
5
6
7
8
9
R2
R4
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
2
2
-
5
∞
1
∞
∞
∞
∞
3
3
∞
4
-
1
5
∞
∞
∞
∞
3
R1
R6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
R8
2
6
4
∞
∞
∞
3
-
2
1
∞
7
∞
∞
∞
4
4
5
-
∞
5
8
5
∞
∞
∞
∞
1
∞
-
2
9
∞
∞
∞
3
∞
∞
3
3
-
Algorithm จะหยุดเมื่อถึงจํานวน Hop สูงสุดของ NW
Algorithm สามารถคํานวณได้แม้ว่าจะไม่รู้ Topology โดยการร ับข้อมูลจาก Node ข้างเคียง แล้วมา Update ตารางของต ัวเอง โดยใช้ค่า Cost ที่ตํ่ากว่า
Dijkstra’s Algorithm
Definitions
Find shortest paths from given source node to all other nodes, by developing paths in order of increasing path length
N = set of nodes in the network
s = source node
T = set of nodes so far incorporated by the algorithm
w(i, j) =
link cost from node i to node j
w(i, i) = 0
w(i, j) = ∞ if the two nodes are not directly connected
w(i, j) ≥ 0 if the two nodes are directly connected
L(n) = cost of least-cost path from node s to node n currently known
At termination, L(n) is cost of least-cost path from s to n
Dijkstra’s Algorithm Method
Step 1 [Initialization]
T = {s} Set of nodes so far incorporated consists of only source node
L(n) = w(s, n) for n ≠ s
Initial path costs to neighboring nodes are simply link costs
Step 2 [Get Next Node]
Find neighboring node not in T with least-cost path from s
Incorporate node into T
Also incorporate the edge that is incident on that node and a node in T that contributes to the path
Step 3 [Update Least-Cost Paths]
L(n) = min[L(n), L(x) + w(x, n)] for all n ∉ T
If latter term is minimum, path from s to n is path from s to x concatenated with edge from x to n
Algorithm terminates when all nodes have been added to T
Example: Dijkstra จาก Node 1
(T={1})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1}, L(2)=3,L(3)=inf,L(4)=inf,
8
5
∞
∞
∞
∞
1
∞
-
2
L(5)=inf,L(6)=6,L(7)=inf,L(8)=2,
9
∞
∞
∞
3
∞
∞
3
3
-
L(9)=inf
Example: Dijkstra จาก Node 1
(T={1})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1}, L(2)=3,L(3)=inf,L(4)=inf,
8
5
∞
∞
∞
∞
1
∞
-
2
L(5)=inf,L(6)=6,L(7)=inf, L(8)=2,
9
∞
∞
∞
3
∞
∞
3
3
-
L(9)=inf
Min = L(8) ด ังน ั้นนํา Node 8 ใส่ใน T; T={1,8}
L(n) = min[L(n), L(8) + w(8, n)] for all n not in T
T={1,8}, L(2)=3,L(3)=inf,L(4)=inf,
L(5)=inf, L(6)=3, L(7)=inf,L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,8})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,8}, L(2)=3, L(3)=inf,L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2
L(5)=inf,L(6)=3,L(7)=inf, L(8)=2,
9
∞
∞
∞
3
∞
∞
3
3
-
L(9)=4
Min = L(2) ด ังน ั้นนํา Node 2 ใส่ใน T; T={1,2,8}
L(n) = min[L(n), L(2) + w(2, n)] for all n not in T
T={1,2,8}, L(2)=3, L(3)=8, L(4)=inf,
L(5)=4, L(6)=3, L(7)=inf, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,8})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,2,8}, L(2)=3, L(3)=8,L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2
L(5)=4, L(6)=3, L(7)=inf, L(8)=2,
9
∞
∞
∞
3
∞
∞
3
3
-
L(9)=4
Min = L(6) ด ังน ั้นนํา Node 6 ใส่ใน T; T={1,2,6,8}
L(n) = min[L(n), L(6) + w(6, n)] for all n not in T
T={1,2,6,8}, L(2)=3, L(3)=8, L(4)=inf,
L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,6,8})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,2,6,8}, L(2)=3, L(3)=8,L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2
L(5)=4, L(6)=3, L(7)=5, L(8)=2,
9
∞
∞
∞
3
∞
∞
3
3
-
L(9)=4
Min = L(5) หรือ L(9) ก็ได้ ด ังน ั้นนํา Node 5 ใส่ใน T; T={1,2,5,6,8}
L(n) = min[L(n), L(5) + w(5, n)] for all n not in T
T={1,2,5,6,8}, L(2)=3, L(3)=6, L(4)=inf,
L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,5,6,8})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,2,5,6,8}, L(2)=3, L(3)=6, L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2
L(5)=4, L(6)=3, L(7)=5, L(8)=2,
9
∞
∞
∞
3
∞
∞
3
3
-
L(9)=4
Min = L(9) ด ังน ั้นนํา Node 9 ใส่ใน T; T={1,2,5,6,8,9}
L(n) = min[L(n), L(9) + w(9, n)] for all n not in T
T={1,2,5,6,8,9}, L(2)=3, L(3)=6, L(4)=7,
L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,5,6,8,9})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,2,5,6,8,9}, L(2)=3, L(3)=6,
8
5
∞
∞
∞
∞
1
∞
-
2
L(4)=7, L(5)=4, L(6)=3, L(7)=5,
9
∞
∞
∞
3
∞
∞
3
3
-
L(8)=2, L(9)=4
Min = L(7) ด ังน ั้นนํา Node 7 ใส่ใน T; T={1,2,5,6,7,8,9}
L(n) = min[L(n), L(7) + w(7, n)] for all n not in T
T={1,2,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7,
L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,5,6,7,8,9})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,2,5,6,7,8,9}, L(2)=3, L(3)=6,
8
5
∞
∞
∞
∞
1
∞
-
2
L(4)=7, L(5)=4, L(6)=3, L(7)=5,
9
∞
∞
∞
3
∞
∞
3
3
-
L(8)=2, L(9)=4
Min = L(3) ด ังน ั้นนํา Node 3 ใส่ใน T; T={1,2,3,5,6,7,8,9}
L(n) = min[L(n), L(3) + w(3, n)] for all n not in T
T={1,2,3,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7, L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,3,5,6,7,8,9})
R3
5
1
1
2
3
4
5
6
7
8
9
R2
R4
4
2
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
5
2
2
-
5
∞
1
∞
∞
∞
∞
2
2
3
4
3
4
3
∞
4
-
1
5
∞
∞
∞
∞
4
1
3 3 3
R1
R6
6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
4
5
5
1
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
3
R8
5
2
6
4
∞
∞
∞
3
-
2
1
∞
3
7
∞
∞
∞
4
4
5
-
∞
5
T={1,2,3,5,6,7,8,9}, L(2)=3, L(3)=6,
8
5
∞
∞
∞
∞
1
∞
-
2
L(4)=7, L(5)=4, L(6)=3, L(7)=5,
9
∞
∞
∞
3
∞
∞
3
3
-
L(8)=2, L(9)=4
Min = L(4) ด ังน ั้นนํา Node 4 ใส่ใน T; T={1,2,3,4,5,6,7,8,9}
L(n) = min[L(n), L(4) + w(4, n)] for all n not in T
T={1,2,3,4,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7, L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4
Example: Dijkstra จาก Node 1
(T={1,2,3,4,5,6,7,8,9})
R3
1
2
3
4
5
6
7
8
9
R2
R4
2
1
-
3
∞
∞
∞
6
∞
2
∞
1
R5
2
2
-
5
∞
1
∞
∞
∞
∞
3
3
∞
4
-
1
5
∞
∞
∞
∞
3
R1
R6
2
4
∞
∞
2
-
∞
∞
3
∞
3
R7
R9 5
∞
2
2
∞
-
4
1
∞
∞
2 1
R8
2
6
4
∞
∞
∞
3
-
2
1
∞
7
∞
∞
∞
4
4
5
-
∞
5
8
5
∞
∞
∞
∞
1
∞
-
2
9
∞
∞
∞
3
∞
∞
3
3
-
T={1,2,3,4,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7, L(5)=4, L(6)=3, L(7)=5, L(8)=2,
L(9)=4 Algorithm Terminates
Dijkstra จะคํานวณได้ต่อเมื่อรู้ Topology ของ Network
HW # 7
Download และส่งส ัปดาห ์หน้า
End of Week 12
Week 13 IP Routing II:
BGP/RIP/OSPF and Multicast
Protocols
Chapter 27:27.9-27.16 + Extra Notes
BGP
RIP
OSPF
Subnet and VLAN
Switch Layer 3